package stack;

import java.util.*;

public class KuoHao {
    /*
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
     */
    public boolean isValid(String s) {
        if(s.length() == 0 || s == null){
            return false;
        }
        if(s.length()==1){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i) == '('||s.charAt(i) == '[' || s.charAt(i) == '{'){
                stack.push(s.charAt(i));
            }
            if(s.charAt(i)==')'&&stack.isEmpty()){
                return false;
            }
            if(s.charAt(i)=='}'&&stack.isEmpty()){
                return false;
            }
            if(s.charAt(i)==']'&&stack.isEmpty()){
                return false;
            }
            if(s.charAt(i)==')'&&!stack.pop().equals('(')){
                return false;
            }
            if(s.charAt(i) == ']'&&!stack.pop().equals('[')){
                return false;
            }
            if(s.charAt(i) == '}' &&!stack.pop().equals('{')){
                return false;
            }

        }
        if(!stack.isEmpty()){
            return false;
        }
            return true;
    }
}
class MinStack{
  /*
  设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
   */
   Node root;

  public MinStack() {
    root = new Node();
  }

    public void push(int val) {
        Node node = new Node(val,root.next);
        node.min = root.min;
        root.next = node;
        root.min = Math.min(root.min,val);
    }

    public void pop() {
        Node cur = root.next;
        if(cur.val == root.min){
            root.min = cur.min;
        }
        root.next = cur.next;
        cur.next = null;
    }

    public int top() {
        return root.next.val;
    }

    public int getMin() {
        return root.min;
    }
}
class Node{
    int min;
    int val;
    Node next;
    Node(){
        min = Integer.MAX_VALUE;
    }
    Node(int val){
        this.val = val;
    }
    Node(int val, Node next){
        this.val = val;
        this.next = next;
    }
}
class Password{
    /*
    给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
     */
    public String decodeString(String s) {
        if(s==null || s.length() == 0){
            return "";
        }
        String str = "";
        char ch[] = s.toCharArray();
        int num = 0;
        Stack<Integer> s_int = new Stack<>();
        Stack<String> s_string = new Stack<>();
        for(int  i = 0;i < ch.length;i++){
            if(ch[i] >= '0' && ch[i]<='9'){
                num = num * 10 + ch[i] - '0';
            }else if(ch[i] == '['){
                s_string.push(str);
                s_int.push(num);
                num = 0;
                str = "";
            }else if(ch[i] == ']'){
                String temp = s_string.pop();
                int count = s_int.pop();
                for(int j = 0;j<count;j++){
                    temp += str;
                }
                str = temp;
            }else{
                str+=ch[i];
            }
        }
        return str;
    }
}
class Temperature{
    /*
    给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
     */
    public int[] dailyTemperatures(int[] temperatures) {
            int n = temperatures.length;
            Deque<Integer> stack = new ArrayDeque<>();
            int [] ans = new int[n];
            for(int i=n-1;i>=0;i--){
                int t = temperatures[i];
                while(!stack.isEmpty()&&t>=temperatures[stack.peek()]) stack.pop();
                if(!stack.isEmpty()) ans[i]=stack.peek()-i;
                stack.push(i);
            }
            return ans;
    }
}
class Max_Rect{
    /*
    给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
     */
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        int []tmp = new int [heights.length + 2];
        System.arraycopy(heights,0,tmp,1,heights.length);
        for(int i = 0;i<tmp.length;i++){
            while(!stack.isEmpty()&&tmp[i] < tmp[stack.peek()]){
                Integer h = tmp[stack.pop()];
                max = Math.max(max,(i - stack.peek() - 1 ) * h);
            }
            stack.push(i);
        }
        return max;
    }
    /*
    给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
请你返回 好 子数组的最大可能 分数 。
示例 1：
输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
示例 2：
输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
     */
    public int maximumScore(int[] nums, int k) {
       return 0;
    }
}
class Test{
    public static void main(String[] args) {
        int nums[] = {1,4,3,7,4,5};
        Max_Rect maxRect = new Max_Rect();
        int i = maxRect.maximumScore(nums, 5);
    }
}
